package _go

/*912. 排序数组
难度
中等

413

收藏

分享
切换为英文
接收动态
反馈
给你一个整数数组 nums，请你将该数组升序排列。



示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]


提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
*/

//归并排序 分治法
func sortArray(nums []int) []int {
	//递归退出的条件
	if len(nums) <= 1 {
		return nums
	}

	//找到中间点 分成两个进行递归
	p := len(nums) / 2
	left := sortArray(nums[:p])
	right := sortArray(nums[p:])
	//将两个已经有序的数据进行合并
	return mergeAry(left, right)
}

//合并的方法
func mergeAry(left, right []int) []int {
	leftLen := len(left)
	rightLen := len(right)
	//简单的错误判断 有一个是空直接返回就好
	if leftLen == 0 {
		return right
	}
	if rightLen == 0 {
		return right
	}
	//两个数据的指针 标识当前的各自指向的数据
	i, j := 0, 0
	res := []int{}
	//开始循环 知道一个切片为空
	for i < leftLen && j < rightLen {
		//如果left数据的数据小于right的数据 那么将小的加入结果集中 并且移动小的切片的指针
		if left[i] <= right[j] {
			//加入结果 且 i向后移动
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
			j++
		}
	}

	//处理剩余的没有完成的数据 因为有可能两个切片就是有序的 需要将没有处理的切片直接赋值到结果集中
	if i == leftLen {
		res = append(res, right[j:]...)
	} else {
		res = append(res, left[i:]...)
	}
	return res
}

//快拍 快拍的思想也是类似分治
//先选出来一个基点值 作比较 将小于基准值的都放在左边
//大于的都放在右边  然后在递归对左边和右边进行快拍
func qsortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	//调用递归函数
	qSort(nums, 0, len(nums)-1)
	return nums
}
func qSort(nums []int, l, r int) {
	//函数的退出条件
	if l < r {
		//切割函数
		p := ppen(nums, l, r)
		//已经按中间值排好序  所以中间的数就不用排序了
		qSort(nums, l, p-1)
		qSort(nums, p+1, r)
	}
}

//分割函数
func ppen(nums []int, l, r int) int {
	//就一个数了 不用排序
	if len(nums) <= 1 {
		return l
	}

	//选择一个基点数  随机也可以
	p := l
	//找到基准点的值
	pNumsValue := nums[p]
	//结束条件  左右两个指针相等就退出  说明已经将两个数组排号序了
	for l < r {
		//这个地方有个大坑  必须要从右边开始移动
		//因为需要保证r > p 就需要r移动 如果先移动l那就是只能保证 l <= p 不能保证 r >= p
		//先右开始找到一个小于基准点的数 没有就直接想前移动
		for l < r && nums[r] >= pNumsValue {
			r--
		}
		//从做向右找到一个大于基准点的数
		for l < r && nums[l] <= pNumsValue {
			l++
		}
		//没找到就返回
		if l >= r {
			break
		}
		//交换两个不符合要求的数 这样就使得两个数都是符合规则的 小于的在左边 大于的在右边
		nums[l], nums[r] = nums[r], nums[l]
		//fmt.Printf("nums %+v h:%d t:%d \n",nums, l, r )
	}
	//基准位归位
	//这个很重要
	//最后要把基准点的数交换回去 因为基准点动一开始就没有移动过
	nums[p], nums[l] = nums[l], nums[p]
	//fmt.Printf("nums %+v p:%d h:%d \n",nums, p, l )
	//返回作左右应该都可以  因为他俩是相等的
	return l
}
